package 队列与栈;

import 链表题目.model.ListNode;

import java.util.Stack;

//重排链表
//https://leetcode.cn/problems/reorder-list/
class 重排链表 {
    public void reorderList(ListNode head) {
        Stack<ListNode> hStack = new Stack<>();
        ListNode p = head;
        while (p != null) {
            hStack.push(p);
            p = p.next;
        }
        p = head;
        while (p != null) {
            ListNode pNode = hStack.pop();
            ListNode next = p.next;
            if (pNode == next || pNode.next == next) {
                // 结束条件，链表节点数为奇数或偶数时均适用
                pNode.next = null;
                break;
            }
            p.next = pNode;
            pNode.next = next;
            p = next;
        }
    }

    public static void main(String[] args) {
        重排链表 solution = new 重排链表();
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        solution.reorderList(head);
    }
}
